// `gec::hash::Hash` and `gec::hash::hash_combine` are modified version of
// `hash` and `hash_combine` from
// [Boost.ContainerHash](https://www.boost.org/doc/libs/1_79_0/libs/container_hash/doc/html/hash.html)
// by Daniel James and Peter Dimov. Some necessary function modifiers are added
// such that they are compatible with CUDA
//
// ----- Boost.ContainerHash License Header -----
// Copyright 2005-2014 Daniel James.
// Copyright 2021 Peter Dimov.
// Distributed under the Boost Software License, Version 1.0.
// https://www.boost.org/LICENSE_1_0.txt
//
// ----- Boost Software License, Version 1.0 -----
// Boost Software License - Version 1.0 - August 17th, 2003
//
// Permission is hereby granted, free of charge, to any person or organization
// obtaining a copy of the software and accompanying documentation covered by
// this license (the "Software") to use, reproduce, display, distribute,
// execute, and transmit the Software, and to prepare derivative works of the
// Software, and to permit third-parties to whom the Software is furnished to
// do so, all subject to the following:
//
// The copyright notices in the Software and this entire statement, including
// the above license grant, this restriction and the following disclaimer,
// must be included in all copies of the Software, in whole or in part, and
// all derivative works of the Software, unless such copies or derivative
// works are solely in the form of machine-executable object code generated by
// a source language processor.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
// SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
// FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
// DEALINGS IN THE SOFTWARE.

#pragma once
#ifndef GEC_UTILS_HASH_HPP
#define GEC_UTILS_HASH_HPP

#include "basic.hpp"

#include <climits>
#include <cstring>
#include <type_traits>

namespace gec {

namespace hash {

namespace _hash_integral_ {

template <class T, bool bigger_than_size_t = (sizeof(T) > sizeof(size_t)),
          size_t size_t_bits = sizeof(size_t) * CHAR_BIT,
          size_t type_bits = sizeof(T) * CHAR_BIT>
struct HashIntegral;

template <class T, size_t size_t_bits, size_t type_bits>
struct HashIntegral<T, false, size_t_bits, type_bits> {
    GEC_HD static size_t call(T v) { return static_cast<size_t>(v); }
};

template <class T>
struct HashIntegral<T, true, 32, 64> {
    GEC_HD static size_t call(T v) {
        size_t seed = 0;

        seed ^= static_cast<size_t>(v >> 32) + (seed << 6) + (seed >> 2);
        seed ^= static_cast<size_t>(v) + (seed << 6) + (seed >> 2);

        return seed;
    }
};

template <class T>
struct HashIntegral<T, true, 32, 128> {
    GEC_HD static size_t call(T v) {
        size_t seed = 0;

        seed ^= static_cast<size_t>(v >> 96) + (seed << 6) + (seed >> 2);
        seed ^= static_cast<size_t>(v >> 64) + (seed << 6) + (seed >> 2);
        seed ^= static_cast<size_t>(v >> 32) + (seed << 6) + (seed >> 2);
        seed ^= static_cast<size_t>(v) + (seed << 6) + (seed >> 2);

        return seed;
    }
};

template <class T>
struct HashIntegral<T, true, 64, 128> {
    GEC_HD static size_t call(T v) {
        size_t seed = 0;

        seed ^= static_cast<size_t>(v >> 64) + (seed << 6) + (seed >> 2);
        seed ^= static_cast<size_t>(v) + (seed << 6) + (seed >> 2);

        return seed;
    }
};

} // namespace _hash_integral_

template <typename T>
typename std::enable_if_t<
    std::is_integral<T>::value && std::is_unsigned<T>::value, size_t>
    GEC_HD hash_value(T v) {
    return _hash_integral_::HashIntegral<T>::call(v);
}

template <typename T>
typename std::enable_if_t<
    std::is_integral<T>::value && std::is_signed<T>::value, size_t>
    GEC_HD hash_value(T v) {
    using U = typename std::make_unsigned<T>::type;

    if (v >= 0) {
        return hash_value(static_cast<U>(v));
    } else {
        return ~hash_value(static_cast<U>(~static_cast<U>(v)));
    }
}

// enumeration types

template <typename T>
GEC_HD typename std::enable_if_t<std::is_enum<T>::value, size_t>
hash_value(T v) {
    return static_cast<size_t>(v);
}

// floating point types

namespace _hash_float_ {

template <class T, size_t Bits = sizeof(T) * CHAR_BIT,
          int Digits = utils::type_bits<T>::value,
          size_t size_t_bits = sizeof(size_t) * CHAR_BIT>
struct HashFloat;

// float
template <class T, int Digits, size_t size_t_bits>
struct HashFloat<T, 32, Digits, size_t_bits> {
    GEC_HD static size_t call(T v) {
        uint32_t w;
        memcpy(&w, &v, sizeof(v));

        return w;
    }
};

// double
template <class T, int Digits>
struct HashFloat<T, 64, Digits, 64> {
    GEC_HD static size_t call(T v) {
        uint64_t w;
        memcpy(&w, &v, sizeof(v));

        return w;
    }
};

template <class T, int Digits>
struct HashFloat<T, 64, Digits, 32> {
    GEC_HD static size_t call(T v) {
        uint32_t w[2];
        memcpy(&w, &v, sizeof(v));

        size_t seed = 0;

        seed ^= static_cast<size_t>(w[0]) + (seed << 6) + (seed >> 2);
        seed ^= static_cast<size_t>(w[1]) + (seed << 6) + (seed >> 2);

        return seed;
    }
};

// 80 bit long double in 12 bytes
template <class T>
struct HashFloat<T, 96, 64, 64> {
    GEC_HD static size_t call(T v) {
        uint64_t w[2] = {};
        memcpy(&w, &v, 80 / CHAR_BIT);

        size_t seed = 0;

        seed ^= static_cast<size_t>(w[0]) + (seed << 6) + (seed >> 2);
        seed ^= static_cast<size_t>(w[1]) + (seed << 6) + (seed >> 2);

        return seed;
    }
};

template <class T>
struct HashFloat<T, 96, 64, 32> {
    GEC_HD static size_t call(T v) {
        uint32_t w[3] = {};
        memcpy(&w, &v, 80 / CHAR_BIT);

        size_t seed = 0;

        seed ^= static_cast<size_t>(w[0]) + (seed << 6) + (seed >> 2);
        seed ^= static_cast<size_t>(w[1]) + (seed << 6) + (seed >> 2);
        seed ^= static_cast<size_t>(w[2]) + (seed << 6) + (seed >> 2);

        return seed;
    }
};

// 80 bit long double in 16 bytes
template <class T>
struct HashFloat<T, 128, 64, 64> {
    GEC_HD static size_t call(T v) {
        uint64_t w[2] = {};
        memcpy(&w, &v, 80 / CHAR_BIT);

        size_t seed = 0;

        seed ^= static_cast<size_t>(w[0]) + (seed << 6) + (seed >> 2);
        seed ^= static_cast<size_t>(w[1]) + (seed << 6) + (seed >> 2);

        return seed;
    }
};

template <class T>
struct HashFloat<T, 128, 64, 32> {
    GEC_HD static size_t call(T v) {
        uint32_t w[3] = {};
        memcpy(&w, &v, 80 / CHAR_BIT);

        size_t seed = 0;

        seed ^= static_cast<size_t>(w[0]) + (seed << 6) + (seed >> 2);
        seed ^= static_cast<size_t>(w[1]) + (seed << 6) + (seed >> 2);
        seed ^= static_cast<size_t>(w[2]) + (seed << 6) + (seed >> 2);

        return seed;
    }
};

// 128 bit long double
template <class T, int Digits>
struct HashFloat<T, 128, Digits, 64> {
    GEC_HD static size_t call(T v) {
        uint64_t w[2];
        memcpy(&w, &v, sizeof(v));

        size_t seed = 0;

        seed ^= static_cast<size_t>(w[0]) + (seed << 6) + (seed >> 2);
        seed ^= static_cast<size_t>(w[1]) + (seed << 6) + (seed >> 2);

        return seed;
    }
};

template <class T, int Digits>
struct HashFloat<T, 128, Digits, 32> {
    GEC_HD static size_t call(T v) {
        uint32_t w[4];
        memcpy(&w, &v, sizeof(v));

        size_t seed = 0;

        seed ^= static_cast<size_t>(w[0]) + (seed << 6) + (seed >> 2);
        seed ^= static_cast<size_t>(w[1]) + (seed << 6) + (seed >> 2);
        seed ^= static_cast<size_t>(w[2]) + (seed << 6) + (seed >> 2);
        seed ^= static_cast<size_t>(w[3]) + (seed << 6) + (seed >> 2);

        return seed;
    }
};

} // namespace _hash_float_

template <typename T>
GEC_HD typename std::enable_if_t<std::is_floating_point<T>::value, size_t>
hash_value(T v) {
    return _hash_float_::HashFloat<T>::call(v + 0);
}

// pointer types

// Implementation by Alberto Barbati and Dave Harris.
template <class T>
GEC_HD size_t hash_value(T *const &v) {
    size_t x = static_cast<size_t>(reinterpret_cast<uintptr_t>(v));
    return x + (x >> 3);
}

template <class T>
struct GEC_EMPTY_BASES Hash {
    using argument_type = T;
    using result_type = size_t;

    GEC_HD size_t operator()(T const &val) const { return hash_value(val); }
};

namespace _hash_combine_ {

GEC_HD GEC_INLINE uint32_t rotl32(uint32_t x, int r) {
#ifdef __CUDA_ARCH__
    return __funnelshift_l(x, x, r);
#else
#ifdef _MSC_VER
    return _rotl(x, r);
#else
    return (x << r) | (x >> (32 - r));
#endif // _MSC_VER
#endif // __CUDA_ARCH__
}

template <size_t Bits>
struct HashCombine {
    template <typename SizeT>
    inline static SizeT call(SizeT seed, SizeT value) {
        seed ^= value + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        return seed;
    }
};

template <>
struct HashCombine<32> {
    GEC_HD GEC_INLINE static uint32_t call(uint32_t h1, uint32_t k1) {
        constexpr uint32_t c1 = 0xcc9e2d51;
        constexpr uint32_t c2 = 0x1b873593;

        k1 *= c1;
        k1 = rotl32(k1, 15);
        k1 *= c2;

        h1 ^= k1;
        h1 = rotl32(h1, 13);
        h1 = h1 * 5 + 0xe6546b64;

        return h1;
    }
};

template <>
struct HashCombine<64> {
    GEC_HD GEC_INLINE static uint64_t call(uint64_t h, uint64_t k) {
        constexpr uint64_t m = 0xc6a4a7935bd1e995ull;
        constexpr int r = 47;

        k *= m;
        k ^= k >> r;
        k *= m;

        h ^= k;
        h *= m;

        // Completely arbitrary number, to prevent 0's
        // from hashing to 0.
        h += 0xe6546b64;

        return h;
    }
};

} // namespace _hash_combine_

#if defined(GEC_MSVC)
#pragma warning(push)
#if defined(_MSC_VER) && _MSC_VER <= 1400
#pragma warning(disable : 4267) // 'argument' : conversion from 'size_t' to
                                // 'unsigned int', possible loss of data
                                // A misguided attempt to detect 64-bit
                                // incompatability.
#endif
#endif

GEC_HD GEC_INLINE void hash_combine(size_t &seed, size_t v) {

    seed = _hash_combine_::HashCombine<utils::type_bits<size_t>::value>::call(
        seed, v);
}

#if defined(GEC_MSVC)
#pragma warning(pop)
#endif

template <typename LIMB_T, size_t LIMB_N, typename Hasher = Hash<LIMB_T>>
struct SeqHasher {
    GEC_HD GEC_INLINE static void call(size_t &seed, const LIMB_T *arr,
                                       const Hasher &hasher) {
        hash_combine(seed, hasher(*arr));
        SeqHasher<LIMB_T, LIMB_N - 1, Hasher>::call(seed, arr + 1, hasher);
    }
};
template <typename LIMB_T, typename Hasher>
struct SeqHasher<LIMB_T, 0, Hasher> {
    GEC_HD GEC_INLINE static void call(size_t &, const LIMB_T *,
                                       const Hasher &) {}
};

} // namespace hash

} // namespace gec

#endif // !GEC_UTILS_HASH_HPP
